#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
// 跳跃游戏I
// 位于最初的下标，判断能否到达最后一个下标位置
// 【贪心算法】不断维护一个最大可达到的距离
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return true;
        int max_dist = 0;
        for (int i=0; i<=min(n-1, max_dist); ++i) {
            max_dist = max(max_dist, i+nums[i]);
            if (max_dist >= n-1) return true;  // 剪枝
        }
        return max_dist >= n-1;
    }

// 跳跃游戏II [45]
// 用最少的跳跃次数到达数组的最后一个位置
// 假设总是可以到达数组最后的位置
// 【贪心算法】正向：不断去查找能够达到的最远位置
// 维护当前能达到的最远位置，注意 i=0 情况
    int jump(vector<int>& nums) {  // O(n)
        int n = nums.size();
        if (n <= 1) return 0;
        int pos = 0, steps = 0;
        
        // always jumps to the next max location
        while (pos < n-1) {
            int i_step = pos+nums[pos];  // 当前[理论上]最远跳跃位置
            int max_dist = min(n-1, i_step);
            for (int i=pos+1; i<=min(n-1, pos+nums[pos]); ++i) {  // 这里不能用 i_step 代替！
                int far_reach = min(n-1, i+nums[i]);              // 是引用！我们需要一个固定值！
                if (far_reach > max_dist) {
                    max_dist = i+nums[i];
                    i_step = i;
                }
            }
            pos = i_step;
            steps++;
        }
        
        return steps;
    }
};
